Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.

• Input:Digit string "23"
  
• Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

题目大意：给定一个数字组成的字符串，返回所有的这些数字所代表的字母组合。数字字母映射表是与手机上一致

题目难度：Medium

import java.util.ArrayList;
import java.util.List;

/**
 * Created by gzdaijie on 16/5/18
 * 递归,每一个数字有3-4种情况,遇到每一个数字,遍历其所有可能性即可
 */
public class Solution {
    private static final String[] strs = { "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<String>();
        StringBuilder combine = new StringBuilder();

        if (digits == null || digits.length() == 0) return result;

        letterFullPemutation(result, digits, combine, 0);
        return result;
    }

    /**
     * @param result 存储结果
     * @param str 输入的数字
     * @param combine  临时变量,存储当前拼接的字符串
     * @param k 表示当前已经遍历到的位置
     */
    private void letterFullPemutation(List<String> result, String str, StringBuilder combine, int k) {
        // 如果遍历完,而且拼接的字符串不为空,则加入结果当中
        if (k == str.length()) {
            if (combine.length() > 0) {
                result.add(combine.toString());
            }
            return;
        }

        int index = str.charAt(k) - '2';
        if (index < 0) {
            letterFullPemutation(result, str, combine, k + 1);
        } else {
            int len = strs[index].length();
            for (int i = 0; i < len; i++) {
                combine.append(strs[index].charAt(i));
                letterFullPemutation(result, str, combine, k + 1);
                combine.setLength(combine.length() - 1);
            }
        }
    }
}

import java.util.*;

/**
 * Created by gzdaijie on 16/5/18
 * BFS，使用队列实现，每次出队的子串，依次添加当前数字对应的字母，再入队
 */
public class Solution {
    private static final String[] strs = { "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public List<String> letterCombinations(String digits) {
        Queue<String> result = new LinkedList<>();
        if (digits == null || digits.length() == 0) return new ArrayList<>(result);

        String str = strs[digits.charAt(0) - '2'];
        int len = str.length();
        for (int i = 0; i < len; i++) {
            result.add(str.charAt(i) + "");
        }

        for (int i = 1; i < digits.length(); i++) {
            int size = result.size();
            while (size-- > 0) {
                String prefix = result.poll();
                str = strs[digits.charAt(i) - '2'];
                len = str.length();
                for (int j = 0; j < len; j++) {
                    result.add(prefix + str.charAt(j));
                }
            }
        }
        return new ArrayList<>(result);
    }
}